1. Field of the Invention
The present invention relates to communication systems using protocols under the Asynchronous Transfer Mode (ATM) standards. In particular, the present invention relates to scheduling ATM cell transmissions for multiple virtual channels under a variable bit rate service, such as available bandwidth rate (ABR) service.
2. Discussion of the Related Art
Data communication under ATM is set forth in a standard entitled "The ATM Forum Specification, version 4.0" (the "ATM standard"). Under the ATM standard, data exchange between a source system and a destination system is accomplished using one or more packetized data streams ("virtual channels"). Data and control information in each virtual channel are transported by 53-byte data packets or cells ("ATM cells"). In general, under the ATM standard, a virtual channel is set up by a virtual circuit connection under a fixed or constant bit rate service (CBR), or a variable bit rate service (VBR). In fact, under the ATM standard, many CBR and VBR virtual circuits can coexist between a given pair of source and destination systems. In one type of VBR service, known as the "available bandwidth rate service" ("ABR service"), the source and destination systems periodically negotiate for each virtual channel a bit rate according to the traffic condition in all switches along the path of the virtual channel's virtual circuit.
In an ABR virtual circuit, the virtual circuit, the source and destination systems, and all the switches in between, negotiate a "peak cell rate" (PCR), a "minimum cell rate" (MCR), and an "initial cell rate" (ICR). During the life of the virtual circuit, resource management (RM) cells are sent periodically by the source system. Initially, the ATM cells for the virtual channel are sent at the ICR until the first RM cell is sent by the source. Included in the RM cell is an "explicit rate" (ER) field and a "direction" (DIR) field, which are initialized by the source system to the PCR and the value "forward" respectively. Because of the "forward" value in the DIR field, this RM cell is referred to as the "forward RM" (FRM) cell. As the FRM cell traverses the virtual circuit towards the destination system, each switch along the virtual circuit examines the ER field of the FRM cell and, where appropriate, reduces the cell rate specified in that field to indicate the available bandwidth the switch can provide, given its own local traffic condition. If a congestion condition is experienced at the switch, i.e. the instantaneous or immediate rate at which ATM cells are arriving exceeds the rate at which these ATM cells can be processed and forwarded by the switch, a "congestion" field (CI) of the FRM cell is marked. When the FRM cell reaches the destination system, the destination system (i) makes its own adjustment to the ER field, if necessary, (ii) marks the DIR field of the RM cell to indicate that the RM cell is now a "backward" RM (BRM) cell, and (iii) returns the BRM cell to the source system in the reverse direction on the virtual circuit. When the BRM cell reaches the source system, the value in the ER field is examined against the current cell rate. The current cell rate, which is also known as the "allowable cell rate" (ACR), is increased or decreased according to the value in the ER field of the BRM cell returned.
In some applications, e.g. an ATM server, it is necessary to support a very large number of virtual channels (e.g. a 1000 channels) of various fixed and variable bit rates over a given ATM physical media. In such an application, a scheduler coordinates the shared use of the physical media among the large number of virtual channels, so that the use of the physical bandwidth of the physical media can be maximized. In addition, many schedulers provide a "fairness" scheme so that sharing of the available bandwidth among the multiple variable rate virtual channels can be carried out in a predictable manner, and each variable rate virtual channel is given some opportunity to meet its desired cell rate.
One class of fairness schemes is known as the "min-max" fairness schemes. Under a min-max fairness scheme, a system divides the virtual channels into two classes according to their respective cell rates relative to the average cell rate ##EQU1## of the system. In the first class, i.e. those virtual channels having desired cell rates at or below the average cell rate, these virtual channels are provided the desired cell rate. In the second class, i.e. those virtual channels having desired cell rates above the average cell rate, these virtual channels share the remaining bandwidth. Within the second class, the bandwidth can be shared among the virtual channels equally ("unweighted"), or according to some assigned priorities ("weighted"). To ensure robustness under a min-max fairness scheme, the elements in the virtual circuits servicing the virtual channels must be capable of rapid response. Otherwise, data loss may result. For example, consider the case when one congested virtual circuit decreases its cell rate abruptly, thereby relieving the congestion condition at a previously congested element within the virtual circuit. In response to the bandwidth now available at the previous congested element, several virtual circuits may attempt to increase their respective cell rates at the same time. If the readjustment in cell rates in these virtual circuits do not occur rapidly enough, congestion conditions may then reappear at other elements of the network rapidly. Such congestion conditions, if not corrected rapidly, may lead to data loss.
To schedule a large number of virtual channels each having an independent cell rate, a number of different approaches are possible. In one approach, a large number of counters, each assigned to a separate virtual channel, can be provided. Under that approach, a count representing the number of time slots to the next transmission (i.e. the inverse of the cell rate) of the assigned virtual channel is held in such a counter, which is initialized to a predetermined value and updated once per ATM cell time slot. At the scheduled next transmission time ("time-out"), e.g. the count reaches zero, an ATM cell of the assigned virtual channel is sent and the next transmission is scheduled by resetting the counter to the predetermined value. However, the scheduling of this large number of counters is a Herculean task: at any given time, a large number of counters may time-out, so that the ATM cells of a large number of virtual channels may be delayed or skipped, due to the instantaneous congestions which may arise. Consequently, severe rate jitters can be expected in many virtual channels. Further, a counter system, such as described here, is not amenable to providing "fairness" without additional sophisticated management.
Under another approach, a schedule table is allocated in memory to provide an entry for each ATM cell time slot. Software which executes in a central processing unit (CPU) can be used to associate ATM cell time slots with virtual channels. Typically, "events" (e.g. transmission of an ATM cell) of each virtual channel occur at regular intervals according to its assigned cell rate. Such an approach has the advantages of simplicity and flexibility. Such an approach is simple because the schedule table entries are simply read in order and at regularly intervals. If a schedule table entry references a virtual channel, i.e. the virtual channel is scheduled to transmit for the current ATM cell time slot, an ATM cell is retrieved from the virtual channel and transmitted. Flexibility is achieved, for example, by providing different fairness schemes using different control programs executing in the CPU at different times to accommodate different requirements under different traffic conditions.
However, many disadvantages can be found also in the schedule table approach. For example, since the schedule table must accommodate both the highest and the lowest cell rates, and often, a large number of intermediate cell rates as well, the number of ATM cell time slots required in a schedule table can be very large. In addition, a change in cell rate for a virtual channel may result in the need to reschedule a large number of events. For a server application, for example, where many virtual channels may change cell rates simultaneously, the number of events that need to be rescheduled can become impractically large.